package com.guqj.basis.sort;

public class SortTest {

	public static void insertSort(int[] arr){
		int temp = 0;
		for(int i = 0; i < arr.length; i++){
			int j = i -1;
			temp = arr[i];
			for(; j >=0 && temp < arr[j]; j --){
				arr[j+1] = arr[j];
			}
			arr[j + 1] = temp;
		}
		
		for(int i = 0; i < arr.length; i++){
			System.out.print(arr[i] + " ");
		}
	}
	
	public static void quickSort(int[] arr){
		_quickSort(arr, 0, arr.length - 1);
		for(int i = 0; i < arr.length; i++){
			System.out.print(arr[i] + " ");
		}
	}
	
	private static void _quickSort(int[] arr, int low, int high){
		if(low < high){
			int middle = getMiddle(arr, low, high);
			_quickSort(arr, low, middle - 1); //对低字表进行递归排序
			_quickSort(arr, middle + 1, high); //对高字表进行递归排序
		}
	}
	
	private static int getMiddle(int[] arr, int low, int high){
		int tmp = arr[low]; // 数组的第一个作为中轴
		while(low < high){
			while(low < high && arr[high] >= tmp){
				high --;
			}
			arr[low] = arr[high];//比中轴小的记录移到低端
			
			while(low < high && arr[low] <= tmp){
				low ++;
			}
			arr[high] = arr[low]; //比中轴大的记录移到高端
		}
		arr[low] = tmp; //中轴记录到尾
		return low; //返回中轴的位置
	}
	
	public static void selectSort(int[] arr){
		int position = 0;
		for(int i = 0; i < arr.length; i++){
			position = i;
			int j = i + 1;
			int temp = arr[i];
			for(; j < arr.length; j ++){
				if(arr[j] < temp){
					temp = arr[j];
					position = j;
				}
			}
			arr[position] = arr[i];
			arr[i] = temp;
		}
		
		for(int i = 0; i < arr.length; i++){
			System.out.print(arr[i] + " ");
		}
	}
	
	public static void main(String[] args) {
		int[] arr = {49,38,65,97,76,13,27,49,78,34,12};
		//insertSort(arr);
		//selectSort(arr);
		quickSort(arr);
	}
}
